package leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class _22_GenerateParentheses {
    class Solution {
        public List<String> generateParethesis(int n) {
            List<String>[] lists = new LinkedList[n+1];
            return helper(n,lists);
        }

        private List<String> helper(int n , List<String>[] lists) {
            if (lists[n] != null) return lists[n];
            List<String> res = new LinkedList<String>();
            if (n <= 0) {
                lists[0] = new LinkedList<String>(Arrays.asList(""));
                return lists[0];
            }
            else if (n == 1) {
                lists[1] = new LinkedList<String>(Arrays.asList("()"));
                return lists[1];
            }
            for (int i = 0; i <= n-1; i++) {
                List<String> left = helper(n-i-1, lists);
                List<String> inside = helper(i, lists);
                for (String str1 : left){
                    for (String str2 : inside) {
                        res.add(str1 + "(" + str2 + ")");
                    }
                }
            }
            lists[n] = res;
            return res;
        }
    }

    public _22_GenerateParentheses.Solution getSolution() {
        return new Solution();
    }

    public static void main(String[] args) {
        _22_GenerateParentheses c = new _22_GenerateParentheses();
        _22_GenerateParentheses.Solution s = c.getSolution();
        int n = 2;
        List<String> res = s.generateParethesis(n);
        for (String item : res) {
            System.out.println(item);
        }
        System.out.println("finish...");
    }
}
